import java.util.*;

public class SolutionInterview8_8 {
    public String[] permutation(String S) {
        Map<Character,Integer> c=new HashMap<>();
        for (int i = 0; i < 26; i++) {
            c.put((char)(i+'a'),0);
            c.put((char)(i+'A'),0);
        }
        for (char c1 : S.toCharArray()) {
            c.put(c1,c.get(c1)+1);
        }
        List<String> list=new ArrayList<>();
        dfs(c,' ',S.length(),list,new StringBuilder());
        String[] ans=new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i]=list.get(i);
        }
        return ans;
    }

    private void dfs(Map<Character,Integer> c, char last, int n, List<String> list, StringBuilder stringBuilder) {
        if (stringBuilder.length()==n){
            list.add(stringBuilder.toString());
            return;
        }
        for (Map.Entry<Character, Integer> entry : c.entrySet()) {
            if (entry.getKey()!=last){
                for (int i1 = 1; i1 <= entry.getValue(); i1++) {
                    for (int i2 = 0; i2 < i1; i2++) {
                        stringBuilder.append(entry.getKey());
                    }
                    c.put(entry.getKey(),c.get(entry.getKey())-i1);
                    dfs(c,entry.getKey(),n,list,stringBuilder);
                    for (int i2 = 0; i2 < i1; i2++) {
                        stringBuilder.deleteCharAt(stringBuilder.length()-1);
                    }
                    c.put(entry.getKey(),c.get(entry.getKey())+i1);
                }
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new SolutionInterview8_8().permutation("qqe")));
    }
}
